/**
 * Created by L.jp
 * Description:对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
 * User: 86189
 * Date: 2022-09-01
 * Time: 16:51
 */
//回文状态的改变就是解题的关键，如果是回文字符串那么就可以求出最长回文串的长度，回文状态可以通过数组来构造
    //如果i,j位置字符相等，如果j~i大于两个字符，而且j+1~i-1是回文，那么j~i就是回文字符串
public class Solution {
    public int getLongestPalindrome (String A) {
        char[] array=A.toCharArray();
        //回文的状态是变化的，所以可以建立一个布尔类型的数组，表示从i到j位置是否为回文子串
        int n=A.length();
        boolean[][] dp=new boolean[n][n];
        //初始化，从i到i本身一个字符就是回文串
        for(int i=0;i<n;i++){
            dp[i][i]=true;
        }
        int maxLen=1;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                //如果i,j位置的字符相等
                if(array[i]==array[j]){
                    //如果他们之间的字符大于两个字符
                    if(j+1<=i-1){
                        //如果j+1~i-1的字符串是回文的，那么j~i的字符串就是回文的
                        if(dp[j+1][i-1]){
                            dp[j][i]=true;
                        }
                    }else{
                        //i,j之间小于等于两个字符，那么i~j肯定是回文串
                        dp[j][i]=true;
                    }
                }
                //判断是回文串之后就更新最长回文串的长度
                if(dp[j][i]){
                    int len=i-j+1;
                    maxLen=Math.max(len,maxLen);
                }
            }
            
        }
        return maxLen;
    }

}
